#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

class Solution1
{
public:
    void moveZeroes(vector<int>& nums)
    {
        int len = nums.size();

        for (int dest = -1, cur = 0; cur < len; cur++)
        {
            if (nums[cur] != 0)
            {
                dest++;
                swap(nums[dest], nums[cur]);
            }
        }
    }
};

class Solution2
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        int len = arr.size();
        int dest = -1, cur = 0;
        while (1)
        {
            if (arr[cur])
            {
                dest++;
            }
            else
            {
                dest += 2;
            }
            if (dest >= len - 1)
                break;
            cur++;
        }
        if (dest == len)
        {
            arr[len - 1] = 0;
            cur--, dest -= 2;
        }
        while (cur >= 0)
        {
            if (arr[cur])
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

class Solution3
{
public:
    int bitSum(int n)
    {
        int sum = 0;
        while (n > 0)
        {
            int i = 0;
            i = n % 10;
            sum += i * i;
            n = n / 10;
        }
        return sum;
    }
    bool isHappy(int n)
    {
        int slow = n;
        int fast = bitSum(n);
        while (slow != fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }
};

class Solution4
{
public:
    int maxArea(vector<int>& height)
    {
        int n = height.size(), ret = 0;
        for (int left = 0, right = n - 1; left < right;)
        {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};

class Solution5
{
public:
    int triangleNumber(vector<int>& nums)
    {
        int sum = 0;
        sort(nums.begin(), nums.end());
        for (int i = nums.size() - 1; i >= 2; i--)
        {
            int left = 0, right = i - 1;
            while (left < right)
            {

                if (nums[left] + nums[right] > nums[i])
                {
                    sum += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return sum;
    }
};


int main()
{

	return 0;
}